package com.heima.leetcode.practice;

import java.util.LinkedList;
import java.util.ListIterator;

/**
 * leetcode 1047. 删除字符串中的所有相邻重复项
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/6 10:03
 */
public class E1047 {

    /**
     * <h3>方法一：遍历递归法</h3>
     * @param s 待处理的字符串
     * @return 处理后的字符串
     */
    public String removeDuplicates1(String s) {
        char[] array = s.toCharArray();
        boolean hasDuplicate = false;
        StringBuilder builder = new StringBuilder();

        int index = 0;
        while (index < array.length - 1) {
            if (array[index] == array[index + 1]){
                hasDuplicate = true;
                index++; // 跳过重复项
            }else {
                builder.append(array[index]);
            }
            index++;
        }
        if (index == array.length - 1) { // 如果最后两项重复index会移动两格，变成array.length
            builder.append(array[array.length - 1]);
        }

        String result = builder.toString();
        // 递归结束条件：当前处理前没有相邻重复项
        if (!hasDuplicate){
            return result;
        }
        // 当前处理的时候有重复项，处理完后不管有没有都进行下一次递归，递的时候删除重复项
        return removeDuplicates1(result);
        // 归的时候返回处理后的字符串
    }

    /**
     * <h3>方法二：栈的思想，原地操作，效率最高</h3>
     * 每次遍历到元素跟栈顶元素比较，如果和栈顶元素相同则弹栈 否则入栈
     * @param s 待处理的字符串
     * @return 处理后的字符串
     */
    public String removeDuplicates2(String s) {
        char[] array = s.toCharArray();
        int index = 0; // 用于记录结果的结尾索引（不包含），理解为栈顶指针
        for (int i = 0; i < array.length; i++) {
            if (index == 0){ // 栈为空，直接入栈
                array[index++] = array[i];
            } else if (array[index - 1] == array[i]) { // 栈非空且栈顶元素和遍历到的元素相等，弹栈
                index--; // 弹栈
            } else { // 栈非空且栈顶元素和遍历到的元素不相等，入栈
                array[index++] = array[i];
            }
        }
        return new String(array, 0, index); // 开始索引和长度
    }

    /**
     * <h3>方法二：栈的思想，用StringBuilder，效率低一点点</h3>
     * @param s 待处理的字符串
     * @return 处理后的字符串
     */
    public String removeDuplicates3(String s) {
        char[] array = s.toCharArray();
        StringBuilder builder = new StringBuilder();
        for (char c : array) {
            if (!builder.isEmpty() && builder.charAt(builder.length() - 1) == c) {
                // builder.setLength(builder.length() - 1);
                builder.deleteCharAt(builder.length() - 1);
            } else {
                builder.append(c);
            }
        }
        return builder.toString();
    }

    /**
     * <h3>方法三：栈的思想，用纯栈，效率低一点点</h3>
     * @param s 待处理的字符串
     * @return 处理后的字符串
     */
    public String removeDuplicates4(String s) {
        char[] array = s.toCharArray();
        LinkedList<Character> stack = new LinkedList<>();
        for (char c : array) {
            if (stack.isEmpty()){
                stack.push(c);
            } else if (stack.peek().equals(c)) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        StringBuilder builder = new StringBuilder();
        ListIterator<Character> iterator = stack.listIterator(stack.size());
        while (iterator.hasPrevious()){
            builder.append(iterator.previous());
        }
        return builder.toString();
    }
}
